package demo1;

/**
 * 归并排序
 */
public class mergeSortTest {
    public static void main(String[] args) {
        Node head = new Node(3);
        head.next = new Node(1);
        head.next.next = new Node(9);
        head.next.next.next = new Node(5);
        head.print();
        System.out.println();
        mergeSort(head).print();
    }


    public static Node mergeSort(Node head){
        if(head==null || head.next == null) return head;
        Node middleHead = getMiddleHead(head);
        return merge(mergeSort(head),mergeSort(middleHead));
    }

    // 合并两个有序链表
    public static Node merge(Node p,Node q){
        Node dummy = new Node(-1);
        Node flag = dummy;
        while(p!=null&&q!=null){
            if(p.val < q.val){
                flag.next = p;
                p = p.next;
            }else{
                flag.next = q;
                q = q.next;
            }
            flag = flag.next;
        }

        if(p!=null) flag.next = p;
        if(q!=null) flag.next = q;

        return dummy.next;

    }


    // 把链表一份为二
    public static Node getMiddleHead(Node node){
        Node p = node;
        Node fast = p;
        Node slow = p;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }

        Node middleHead = slow.next;
        slow.next = null;  // 断开
        return middleHead;
    }

}

class Node{
    int val;
    Node next;
    public Node(int val){
        this.val = val;
    }

    void print(){
        Node  p = this;
        while(p!=null){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }

}